The Runtime Complexity (full) of the given CpxTRS could be proven to be BOUNDS(2^n, INF).

(0) Obligation:

Runtime Complexity TRS:
The TRS R consists of the following rules:

0(#) → #
+(x, #) → x
+(#, x) → x
+(0(x), 0(y)) → 0(+(x, y))
+(0(x), 1(y)) → 1(+(x, y))
+(1(x), 0(y)) → 1(+(x, y))
+(1(x), 1(y)) → 0(+(+(x, y), 1(#)))
+(+(x, y), z) → +(x, +(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +(log'(x), 1(#)), #)
*(#, x) → #
*(0(x), y) → 0(*(x, y))
*(1(x), y) → +(0(*(x, y)), y)
*(*(x, y), z) → *(x, *(y, z))
*(x, +(y, z)) → +(*(x, y), *(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +(x, sum(l))
sum(app(l1, l2)) → +(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *(x, prod(l))
prod(app(l1, l2)) → *(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Rewrite Strategy: FULL

(1) DecreasingLoopProof (EQUIVALENT transformation)

The following loop(s) give(s) rise to the lower bound Ω(2ⁿ):
The rewrite sequence
prod(cons(1(x322657_4), l)) →⁺ +(0(*(x322657_4, prod(l))), prod(l))
gives rise to a decreasing loop by considering the right hand sides subterm at position [0,0,1].
The pumping substitution is [l / cons(1(x322657_4), l)].
The result substitution is [ ].

The rewrite sequence
prod(cons(1(x322657_4), l)) →⁺ +(0(*(x322657_4, prod(l))), prod(l))
gives rise to a decreasing loop by considering the right hand sides subterm at position [1].
The pumping substitution is [l / cons(1(x322657_4), l)].
The result substitution is [ ].

(2) BOUNDS(2^n, INF)

(3) RenamingProof (EQUIVALENT transformation)

Renamed function symbols to avoid clashes with predefined symbol.

(4) Obligation:

Runtime Complexity Relative TRS:
The TRS R consists of the following rules:

0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

S is empty.
Rewrite Strategy: FULL

(5) TypeInferenceProof (BOTH BOUNDS(ID, ID) transformation)

Infered types.

(6) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

(7) OrderProof (LOWER BOUND(ID) transformation)

Heuristically decided to analyse the following defined symbols:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(8) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
+', -, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
+' < log'
+' < *'
+' < sum
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(9) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

Induction Base:
+'(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0))

Induction Step:
+'(gen_#:1:true:false3_4(+(n6_4, 1)), gen_#:1:true:false3_4(+(n6_4, 1))) →_R^Ω(1)
0(+'(+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)), 1(#))) →_IH
0(+'(*5_4, 1(#)))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(10) Complex Obligation (BEST)

(11) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
-, eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(12) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)

Induction Base:
-(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

Induction Step:
-(gen_#:1:true:false3_4(+(n109048_4, 1)), gen_#:1:true:false3_4(+(n109048_4, 1))) →_R^Ω(1)
0(-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4))) →_IH
0(gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(13) Complex Obligation (BEST)

(14) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
eq, ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
eq < mem
ge < log'
*' < prod
app < inter
mem < inter

(15) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)

Induction Base:
eq(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
true

Induction Step:
eq(gen_#:1:true:false3_4(+(n111371_4, 1)), gen_#:1:true:false3_4(+(n111371_4, 1))) →_R^Ω(1)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) →_IH
true

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(16) Complex Obligation (BEST)

(17) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
ge, log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
ge < log'
*' < prod
app < inter
mem < inter

(18) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)

Induction Base:
ge(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
true

Induction Step:
ge(gen_#:1:true:false3_4(+(n144082_4, 1)), gen_#:1:true:false3_4(+(n144082_4, 1))) →_R^Ω(1)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) →_IH
true

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(19) Complex Obligation (BEST)

(20) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
log', *', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

(21) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)

Induction Base:
log'(gen_#:1:true:false3_4(+(1, 0)))

Induction Step:
log'(gen_#:1:true:false3_4(+(1, +(n147901_4, 1)))) →_R^Ω(1)
+'(log'(gen_#:1:true:false3_4(+(1, n147901_4))), 1(#)) →_IH
+'(*5_4, 1(#))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(22) Complex Obligation (BEST)

(23) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
*', app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
*' < prod
app < inter
mem < inter

(24) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)

Induction Base:
*'(gen_#:1:true:false3_4(0), gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

Induction Step:
*'(gen_#:1:true:false3_4(+(n244341_4, 1)), gen_#:1:true:false3_4(0)) →_R^Ω(1)
+'(0(*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0))), gen_#:1:true:false3_4(0)) →_IH
+'(0(gen_#:1:true:false3_4(0)), gen_#:1:true:false3_4(0)) →_R^Ω(1)
+'(#, gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(25) Complex Obligation (BEST)

(26) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
app, sum, prod, mem, inter

They will be analysed ascendingly in the following order:
app < inter
mem < inter

(27) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)

Induction Base:
app(gen_nil:cons4_4(0), gen_nil:cons4_4(b)) →_R^Ω(1)
gen_nil:cons4_4(b)

Induction Step:
app(gen_nil:cons4_4(+(n259236_4, 1)), gen_nil:cons4_4(b)) →_R^Ω(1)
cons(#, app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b))) →_IH
cons(#, gen_nil:cons4_4(+(b, c259237_4)))

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(28) Complex Obligation (BEST)

(29) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
sum, prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(30) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)

Induction Base:
sum(gen_nil:cons4_4(0)) →_R^Ω(1)
0(#) →_R^Ω(1)
#

Induction Step:
sum(gen_nil:cons4_4(+(n261271_4, 1))) →_R^Ω(1)
+'(#, sum(gen_nil:cons4_4(n261271_4))) →_IH
+'(#, gen_#:1:true:false3_4(0)) →_R^Ω(1)
#

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(31) Complex Obligation (BEST)

(32) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
prod, mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(33) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n267755₄)

Induction Base:
prod(gen_nil:cons4_4(0))

Induction Step:
prod(gen_nil:cons4_4(+(n267755_4, 1))) →_R^Ω(1)
*'(#, prod(gen_nil:cons4_4(n267755_4))) →_IH
*'(#, *5_4)

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(34) Complex Obligation (BEST)

(35) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n267755₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
mem, inter

They will be analysed ascendingly in the following order:
mem < inter

(36) RewriteLemmaProof (LOWER BOUND(ID) transformation)

Proved the following rewrite lemma:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n279899₄)

Induction Base:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(0))

Induction Step:
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(+(n279899_4, 1))) →_R^Ω(1)
if(eq(gen_#:1:true:false3_4(0), #), true, mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4))) →_L^Ω(1)
if(true, true, mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4))) →_IH
if(true, true, *5_4)

We have rt ∈ Ω(n¹) and sz ∈ O(n). Thus, we have irc_R ∈ Ω(n).

(37) Complex Obligation (BEST)

(38) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n267755₄)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n279899₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

The following defined symbols remain to be analysed:
inter

(39) NoRewriteLemmaProof (LOWER BOUND(ID) transformation)

Could not prove a rewrite lemma for the defined symbol inter.

(40) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n267755₄)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n279899₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(41) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(42) BOUNDS(n^1, INF)

(43) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n267755₄)
mem(gen_#:1:true:false3_4(0), gen_nil:cons4_4(n279899_4)) → *5_4, rt ∈ Ω(n279899₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(44) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(45) BOUNDS(n^1, INF)

(46) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)
prod(gen_nil:cons4_4(n267755_4)) → *5_4, rt ∈ Ω(n267755₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(47) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(48) BOUNDS(n^1, INF)

(49) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)
sum(gen_nil:cons4_4(n261271_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n261271₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(50) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(51) BOUNDS(n^1, INF)

(52) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)
app(gen_nil:cons4_4(n259236_4), gen_nil:cons4_4(b)) → gen_nil:cons4_4(+(n259236_4, b)), rt ∈ Ω(1 + n259236₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(53) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(54) BOUNDS(n^1, INF)

(55) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)
*'(gen_#:1:true:false3_4(n244341_4), gen_#:1:true:false3_4(0)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n244341₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(56) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(57) BOUNDS(n^1, INF)

(58) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)
log'(gen_#:1:true:false3_4(+(1, n147901_4))) → *5_4, rt ∈ Ω(n147901₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(59) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(60) BOUNDS(n^1, INF)

(61) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)
ge(gen_#:1:true:false3_4(n144082_4), gen_#:1:true:false3_4(n144082_4)) → true, rt ∈ Ω(1 + n144082₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(62) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(63) BOUNDS(n^1, INF)

(64) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)
eq(gen_#:1:true:false3_4(n111371_4), gen_#:1:true:false3_4(n111371_4)) → true, rt ∈ Ω(1 + n111371₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(65) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(66) BOUNDS(n^1, INF)

(67) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)
-(gen_#:1:true:false3_4(n109048_4), gen_#:1:true:false3_4(n109048_4)) → gen_#:1:true:false3_4(0), rt ∈ Ω(1 + n109048₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(68) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(69) BOUNDS(n^1, INF)

(70) Obligation:

TRS:
Rules:
0(#) → #
+'(x, #) → x
+'(#, x) → x
+'(0(x), 0(y)) → 0(+'(x, y))
+'(0(x), 1(y)) → 1(+'(x, y))
+'(1(x), 0(y)) → 1(+'(x, y))
+'(1(x), 1(y)) → 0(+'(+'(x, y), 1(#)))
+'(+'(x, y), z) → +'(x, +'(y, z))
-(#, x) → #
-(x, #) → x
-(0(x), 0(y)) → 0(-(x, y))
-(0(x), 1(y)) → 1(-(-(x, y), 1(#)))
-(1(x), 0(y)) → 1(-(x, y))
-(1(x), 1(y)) → 0(-(x, y))
not(true) → false
not(false) → true
if(true, x, y) → x
if(false, x, y) → y
eq(#, #) → true
eq(#, 1(y)) → false
eq(1(x), #) → false
eq(#, 0(y)) → eq(#, y)
eq(0(x), #) → eq(x, #)
eq(1(x), 1(y)) → eq(x, y)
eq(0(x), 1(y)) → false
eq(1(x), 0(y)) → false
eq(0(x), 0(y)) → eq(x, y)
ge(0(x), 0(y)) → ge(x, y)
ge(0(x), 1(y)) → not(ge(y, x))
ge(1(x), 0(y)) → ge(x, y)
ge(1(x), 1(y)) → ge(x, y)
ge(x, #) → true
ge(#, 0(x)) → ge(#, x)
ge(#, 1(x)) → false
log(x) → -(log'(x), 1(#))
log'(#) → #
log'(1(x)) → +'(log'(x), 1(#))
log'(0(x)) → if(ge(x, 1(#)), +'(log'(x), 1(#)), #)
*'(#, x) → #
*'(0(x), y) → 0(*'(x, y))
*'(1(x), y) → +'(0(*'(x, y)), y)
*'(*'(x, y), z) → *'(x, *'(y, z))
*'(x, +'(y, z)) → +'(*'(x, y), *'(x, z))
app(nil, l) → l
app(cons(x, l1), l2) → cons(x, app(l1, l2))
sum(nil) → 0(#)
sum(cons(x, l)) → +'(x, sum(l))
sum(app(l1, l2)) → +'(sum(l1), sum(l2))
prod(nil) → 1(#)
prod(cons(x, l)) → *'(x, prod(l))
prod(app(l1, l2)) → *'(prod(l1), prod(l2))
mem(x, nil) → false
mem(x, cons(y, l)) → if(eq(x, y), true, mem(x, l))
inter(x, nil) → nil
inter(nil, x) → nil
inter(app(l1, l2), l3) → app(inter(l1, l3), inter(l2, l3))
inter(l1, app(l2, l3)) → app(inter(l1, l2), inter(l1, l3))
inter(cons(x, l1), l2) → ifinter(mem(x, l2), x, l1, l2)
inter(l1, cons(x, l2)) → ifinter(mem(x, l1), x, l2, l1)
ifinter(true, x, l1, l2) → cons(x, inter(l1, l2))
ifinter(false, x, l1, l2) → inter(l1, l2)

Types:
0 :: #:1:true:false → #:1:true:false
# :: #:1:true:false
+' :: #:1:true:false → #:1:true:false → #:1:true:false
1 :: #:1:true:false → #:1:true:false
- :: #:1:true:false → #:1:true:false → #:1:true:false
not :: #:1:true:false → #:1:true:false
true :: #:1:true:false
false :: #:1:true:false
if :: #:1:true:false → #:1:true:false → #:1:true:false → #:1:true:false
eq :: #:1:true:false → #:1:true:false → #:1:true:false
ge :: #:1:true:false → #:1:true:false → #:1:true:false
log :: #:1:true:false → #:1:true:false
log' :: #:1:true:false → #:1:true:false
*' :: #:1:true:false → #:1:true:false → #:1:true:false
app :: nil:cons → nil:cons → nil:cons
nil :: nil:cons
cons :: #:1:true:false → nil:cons → nil:cons
sum :: nil:cons → #:1:true:false
prod :: nil:cons → #:1:true:false
mem :: #:1:true:false → nil:cons → #:1:true:false
inter :: nil:cons → nil:cons → nil:cons
ifinter :: #:1:true:false → #:1:true:false → nil:cons → nil:cons → nil:cons
hole_#:1:true:false1_4 :: #:1:true:false
hole_nil:cons2_4 :: nil:cons
gen_#:1:true:false3_4 :: Nat → #:1:true:false
gen_nil:cons4_4 :: Nat → nil:cons

Lemmas:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

Generator Equations:
gen_#:1:true:false3_4(0) ⇔ #
gen_#:1:true:false3_4(+(x, 1)) ⇔ 1(gen_#:1:true:false3_4(x))
gen_nil:cons4_4(0) ⇔ nil
gen_nil:cons4_4(+(x, 1)) ⇔ cons(#, gen_nil:cons4_4(x))

No more defined symbols left to analyse.

(71) LowerBoundsProof (EQUIVALENT transformation)

The lowerbound Ω(n¹) was proven with the following lemma:
+'(gen_#:1:true:false3_4(n6_4), gen_#:1:true:false3_4(n6_4)) → *5_4, rt ∈ Ω(n6₄)

(72) BOUNDS(n^1, INF)